#include <stdio.h>
#include "common_list.h"

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (!headA || !headB) return NULL;

    struct  ListNode *h1 = headA, *h2 = headB;
    int h1_null_cnt = 0, h2_null_cnt = 0;
    while (1) {
        if (!h1) {
            if (h1_null_cnt == 1) return NULL;
            h1 = headB;
            h1_null_cnt++;
        }

        if (!h2) {
            if (h2_null_cnt == 1) return NULL;
            h2 = headA;
            h2_null_cnt++;
        }

        if (h1 == h2)
            return h1;
        
        h1 = h1->next;
        h2 = h2->next;
    }
}

struct ListNode *getIntersectionNode2(struct ListNode *headA, struct ListNode *headB) {

    printf("\n方法2比方1要节省很多代码。实际上，即使2个不想交的链表，同步走，\n\
    也会同时走到对方的结尾（NULL），从而h1==h2,所以不需要判断节点第几次为NULL，只要判断条件只需要有h1 != h2就行");

    struct  ListNode *h1 = headA, *h2 = headB;
    while (h1 != h2) {
        h1 = h1 ? h1->next: headB;
        h2 = h2 ? h2->next: headA;
    }
    return h1;
}

struct ListNode *getIntersectionNode3(struct ListNode *headA, struct ListNode *headB) {

    printf("\n方法3是另一种思路：相交一定在链表的后半段。也就是将2个链表尾部对齐，然后开始同时往后走，如果相同则就是交点");
    printf("\nO -> O -> O -> O -> * -> O ");
    printf("\n          O -> O -> * -> O ");
    printf("\n|  skip | ^              |");

    int lenA = 0, lenB = 0;
    struct  ListNode *h1 = headA, *h2 = headB;
    while (h1) {
        lenA++;
        h1 = h1->next;
    }
    while (h2) {
        lenB++;
        h2 = h2->next;
    }

    h1 = headA;
    h2 = headB;
    if (lenA > lenB) {
        int skip = lenA - lenB;
        while(skip--) {
            h1 = h1->next;
        }
    } else {
        int skip = lenB - lenA;
        while(skip--) {
            h2 = h2->next;
        }
    }

    while (h1 != h2) {
        h1 = h1->next;
        h2 = h2->next;
    }
    return h1;
}

int main(void)
{
    printf("#24. 面试题 02.07. 链表相交\nhttps://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/\n");

    int n1[] = {1,2,3,4};
    int n2[] = {10, 20, 30};

    struct ListNode *l1 = generate_list_val(sizeof(n1)/sizeof(int), n1);
    struct ListNode *l2 = generate_list_val(sizeof(n2)/sizeof(int), n2);
    struct ListNode *l3 = generate_list(5);

    struct ListNode *tmp = l1, *ans;
    while (tmp->next) {
        tmp = tmp->next;
    }
    tmp->next = l3;

    tmp = l2;
    while (tmp->next) {
        tmp = tmp->next;
    }
    tmp->next = l3;
    
    print_list(l1);
    print_list(l2);

    ans = getIntersectionNode(l1, l2);
    print_list(ans);
    ans = getIntersectionNode2(l1, l2);
    print_list(ans);
    ans = getIntersectionNode3(l1, l2);
    print_list(ans);
    return 0;
}